SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Convex optimization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Convex optimization</span></span>

</h1>

</header>

<p><b>Convex optimization</b> is a subfield of <a href="Mathematical_optimization" title="Mathematical optimization">mathematical optimization</a> that studies the problem of minimizing <a href="Convex_function" title="Convex function">convex functions</a> over <a href="Convex_set" title="Convex set">convex sets</a> (or, equivalently, maximizing <a href="Concave_functions" class="mw-redirect" title="Concave functions">concave functions</a> over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms,<sup id="cite_ref-Nesterov_1994_1-0" class="reference"><a href="#cite_note-Nesterov_1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> whereas mathematical optimization is in general <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Abstract_form">Abstract form</h3></div>

<p>A convex optimization problem is defined by two ingredients:<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>The <i>objective function</i>, which is a real-valued <a href="Convex_function" title="Convex function">convex function</a> of <i>n</i> variables, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./54cd4fe3eff3df84e226554864288ef765f82712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.295ex; height:2.676ex;" alt="{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"></span>;</li>

<li>The <i>feasible set</i>, which is a <a href="Convex_subset" class="mw-redirect" title="Convex subset">convex subset</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subseteq \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subseteq \mathbb {R} ^{n}}</annotation>

</semantics>

</math></span><img src="./dc6a0f4c5755d94f15c64ac4d935caf849758248.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.761ex; height:2.509ex;" alt="{\displaystyle C\subseteq \mathbb {R} ^{n}}" loading="lazy"></span>.</li></ul>

<p>The goal of the problem is to find some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x^{\ast }} \in C}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x^{\ast }} \in C}</annotation>

</semantics>

</math></span><img src="./5dfd6962880fb5394efe82f19457dcaa5869d379.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.072ex; height:2.343ex;" alt="{\displaystyle \mathbf {x^{\ast }} \in C}" loading="lazy"></span> attaining

</p>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}</annotation>

</semantics>

</math></span><img src="./11338d87ec69de55dfe7203b056137ac5068978a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.43ex; height:2.843ex;" alt="{\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}" loading="lazy"></span>.</dd></dl>

<p>In general, there are three options regarding the existence of a solution:<sup id="cite_ref-:2_7-0" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.4">: chpt.4 </span></sup>

</p>

<ul><li>If such a point <i>x</i>* exists, it is referred to as an <i>optimal point</i> or <i>solution</i>; the set of all optimal points is called the <i>optimal set</i>; and the problem is called <i>solvable</i>.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is unbounded below over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span>, or the infimum is not attained, then the optimization problem is said to be <i>unbounded</i>.</li>

<li>Otherwise, if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> is the empty set, then the problem is said to be <i>infeasible</i>.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Standard_form">Standard form</h3></div>

<p>A convex optimization problem is in <i>standard form</i> if it is written as

</p>

<mtr>

<mtd>

<mi>minimize</mi>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./607dd620ae52ce049c92f3a8904027845da11911.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:40.261ex; height:10.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>where:<sup id="cite_ref-:2_7-1" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.4">: chpt.4 </span></sup>

</p>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}</annotation>

</semantics>

</math></span><img src="./f33c7feddfbe1e5c87647a55639651d9fb2f23de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.148ex; height:2.343ex;" alt="{\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}" loading="lazy"></span> is the vector of optimization variables;</li>

<li>The objective function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./54cd4fe3eff3df84e226554864288ef765f82712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.295ex; height:2.676ex;" alt="{\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"></span> is a <a href="Convex_function" title="Convex function">convex function</a>;</li>

<li>The inequality constraint functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./4e746cd83540f4c22f2b529d757b47667ddd6d2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.035ex; height:2.676ex;" alt="{\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\ldots ,m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\ldots ,m}</annotation>

</semantics>

</math></span><img src="./74690f54a3c93a332ecb2935e900178b9a555483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.282ex; height:2.509ex;" alt="{\displaystyle i=1,\ldots ,m}" loading="lazy"></span>, are convex functions;</li>

<li>The equality constraint functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./552c7ce8ca2efb69a44f2a1c07851b5b25214816.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.265ex; height:2.676ex;" alt="{\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\ldots ,p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\ldots ,p}</annotation>

</semantics>

</math></span><img src="./5808a63f9673b67baacc3eb77f8547111b94bca9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.411ex; height:2.509ex;" alt="{\displaystyle i=1,\ldots ,p}" loading="lazy"></span>, are <a href="Affine_transformation" title="Affine transformation">affine transformations</a>, that is, of the form: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}</annotation>

</semantics>

</math></span><img src="./2a47fba0b07d9e0b0d66c2808bf0b8aab7141229.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.242ex; height:2.843ex;" alt="{\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a_{i}} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a_{i}} }</annotation>

</semantics>

</math></span><img src="./5b9f1a39a9839d52e673f8db0fcfa68fd2d505ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.056ex; height:2.009ex;" alt="{\displaystyle \mathbf {a_{i}} }" loading="lazy"></span> is a vector and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>

</semantics>

</math></span><img src="./40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy"></span> is a scalar.</li></ul>

<p>The feasible set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> of the optimization problem consists of all points <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} \in {\mathcal {D}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} \in {\mathcal {D}}}</annotation>

</semantics>

</math></span><img src="./b3cd3e80bb6a60b83b06815a137b8e2493eb9809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.044ex; height:2.176ex;" alt="{\displaystyle \mathbf {x} \in {\mathcal {D}}}" loading="lazy"></span> satisfying the inequality and the equality constraints. This set is convex because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation>

</semantics>

</math></span><img src="./3277962e1959c3241fb1b70c7f0ac6dcefebd966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}" loading="lazy"></span> is convex, the <a href="Sublevel_set" class="mw-redirect" title="Sublevel set">sublevel sets</a> of convex functions are convex, affine sets are convex, and the intersection of convex sets is convex.<sup id="cite_ref-:2_7-2" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.2">: chpt.2 </span></sup>

</p><p>Many optimization problems can be equivalently formulated in this standard form. For example, the problem of maximizing a <a href="Concave_function" title="Concave function">concave function</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> can be re-formulated equivalently as the problem of minimizing the convex function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -f}</annotation>

</semantics>

</math></span><img src="./b0edfedee3fca0a26dd6f515e7ed9517a4e2cd04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.087ex; height:2.509ex;" alt="{\displaystyle -f}" loading="lazy"></span>. The problem of maximizing a concave function over a convex set is commonly called a convex optimization problem.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Epigraph_form_(standard_form_with_linear_objective)">Epigraph form (standard form with linear objective)</h3></div>

<p>In the standard form it is possible to assume, without loss of generality, that the objective function <i>f</i> is a <a href="Linear_function" title="Linear function">linear function</a>. This is because any program with a general objective can be transformed into a program with a linear objective by adding a single variable t and a single <a href="Constraint_(mathematics)" title="Constraint (mathematics)">constraint</a>, as follows:<sup id="cite_ref-:02_9-0" class="reference"><a href="#cite_note-:02-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: 1.4">: 1.4 </span></sup>

</p>

<mtr>

<mtd>

<mi>minimize</mi>

<mrow>

</mrow>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./4bf97e01ba09d9a215be68a66b6a882ef1bc60e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:40.261ex; height:13.843ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Conic_form">Conic form</h3></div>

<p>Every convex program can be presented in a <i>conic form</i>, which means minimizing a linear objective over the intersection of an affine plane and a convex cone:<sup id="cite_ref-:02_9-1" class="reference"><a href="#cite_note-:02-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: 5.1">: 5.1 </span></sup>

</p>

<mtr>

<mtd>

<mi>minimize</mi>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./eab912ced035d25c2f4785b8555054f4289eddc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.852ex; margin-bottom: -0.319ex; width:31.276ex; height:7.509ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>where K is a closed <a href="Convex_cone" title="Convex cone">pointed convex cone</a>, L is a <a href="Linear_subspace" title="Linear subspace">linear subspace</a> of R<i><sup>n</sup></i>, and b is a vector in R<i><sup>n</sup></i>. A linear program in standard form is the special case in which K is the nonnegative orthant of R<i><sup>n</sup></i>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Eliminating_linear_equality_constraints">Eliminating linear equality constraints</h3></div><p>

It is possible to convert a convex program in standard form, to a convex program with no equality constraints.<sup id="cite_ref-:2_7-3" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 132">: 132 </span></sup> Denote the equality constraints <i>h<sub>i</sub></i>(<i>x</i>)=0 as <i>Ax</i>=<i>b</i>, where <i>A</i> has <i>n</i> columns. If <i>Ax</i>=<i>b</i> is infeasible, then of course the original problem is infeasible. Otherwise, it has some solution <i>x</i><sub>0</sub> , and the set of all solutions can be presented as: <i>Fz</i>+<i>x</i><sub>0</sub>, where <i>z</i> is in <i>R<sup>k</sup></i>, <i>k</i>=<i>n</i>-rank(<i>A</i>), and <i>F</i> is an <i>n</i>-by-<i>k</i> matrix. Substituting <i>x</i> = <i>Fz</i>+<i>x</i><sub>0</sub> in the original problem gives: </p><blockquote><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}">

<mtr>

<mtd>

<mi>minimize</mi>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./882838d4279e1fff333315c7b8b8f1600a92652d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:47.413ex; height:7.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}" loading="lazy"></span></p></blockquote><p>where the variables are <b>z</b>. Note that there are rank(<i>A</i>) fewer variables. This means that, in principle, one can restrict attention to convex optimization problems without equality constraints. In practice, however, it is often preferred to retain the equality constraints, since they might make some algorithms more efficient, and also make the problem easier to understand and analyze.

</p><div class="mw-heading mw-heading2"><h2 id="Special_cases">Special cases</h2></div>

<p>The following problem classes are all convex optimization problems, or can be reduced to convex optimization problems via simple transformations:<sup id="cite_ref-:2_7-4" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.4">: chpt.4 </span></sup><sup id="cite_ref-rewriting_10-0" class="reference"><a href="#cite_note-rewriting-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Linear_programming" title="Linear programming">Linear programming</a> problems are the simplest convex programs. In LP, the objective and constraint functions are all linear.</li>

<li><a href="Quadratic_programming" title="Quadratic programming">Quadratic programming</a> are the next-simplest. In QP, the constraints are all linear, but the objective may be a convex quadratic function.</li>

<li><a href="Second_order_cone_programming" class="mw-redirect" title="Second order cone programming">Second order cone programming</a> are more general.</li>

<li><a href="Semidefinite_programming" title="Semidefinite programming">Semidefinite programming</a> are more general.</li>

<li><a href="Conic_optimization" title="Conic optimization">Conic optimization</a> are even more general - see figure to the right,</li></ul>

<p>Other special cases include;

</p>

<ul><li><a href="Least_squares" title="Least squares">Least squares</a></li>

<li><a href="Quadratically_constrained_quadratic_programming" class="mw-redirect" title="Quadratically constrained quadratic programming">Quadratic minimization with convex quadratic constraints</a></li>

<li><a href="Geometric_programming" title="Geometric programming">Geometric programming</a></li>

<li><a href="Entropy_maximization" class="mw-redirect" title="Entropy maximization">Entropy maximization</a> with appropriate constraints.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

<p>The following are useful properties of convex optimization problems:<sup id="cite_ref-rockafellar93_11-0" class="reference"><a href="#cite_note-rockafellar93-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:2_7-5" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.4">: chpt.4 </span></sup>

</p>

<ul><li>every point that is <a href="Local_minimum" class="mw-redirect" title="Local minimum">local minimum</a> is also a <a href="Global_minimum" class="mw-redirect" title="Global minimum">global minimum</a>;</li>

<li>the optimal set is convex;</li>

<li>if the objective function is <i>strictly</i> convex, then the problem has at most one optimal point.</li></ul>

<p>These results are used by the theory of convex minimization along with geometric notions from <a href="Functional_analysis" title="Functional analysis">functional analysis</a> (in Hilbert spaces) such as the <a href="Hilbert_projection_theorem" title="Hilbert projection theorem">Hilbert projection theorem</a>, the <a href="Separating_hyperplane_theorem" class="mw-redirect" title="Separating hyperplane theorem">separating hyperplane theorem</a>, and <a href="Farkas'_lemma" title="Farkas' lemma">Farkas' lemma</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Unconstrained_and_equality-constrained_problems">Unconstrained and equality-constrained problems</h3></div>

<p>The convex programs easiest to solve are the <i>unconstrained</i> problems, or the problems with only equality constraints. As the equality constraints are all linear, they can be eliminated with <a href="Linear_algebra" title="Linear algebra">linear algebra</a> and integrated into the objective, thus converting an equality-constrained problem into an unconstrained one.

</p><p>In the class of unconstrained (or equality-constrained) problems, the simplest ones are those in which the objective is <a href="Quadratic_programming" title="Quadratic programming">quadratic</a>. For these problems, the <a href="KKT_conditions" class="mw-redirect" title="KKT conditions">KKT conditions</a> (which are necessary for optimality) are all linear, so they can be solved analytically.<sup id="cite_ref-:2_7-6" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.11">: chpt.11 </span></sup>

</p><p>For unconstrained (or equality-constrained) problems with a general convex objective that is twice-differentiable, <a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a> can be used. It can be seen as reducing a general unconstrained convex problem, to a sequence of quadratic problems.<sup id="cite_ref-:2_7-7" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.11">: chpt.11 </span></sup>Newton's method can be combined with <a href="Line_search" title="Line search">line search</a> for an appropriate step size, and it can be mathematically proven to converge quickly.

</p><p>Other efficient algorithms for unconstrained minimization are <a href="Gradient_descent" title="Gradient descent">gradient descent</a> (a special case of <a href="Method_of_steepest_descent" title="Method of steepest descent">steepest descent</a>).

</p>

<div class="mw-heading mw-heading3"><h3 id="General_problems">General problems</h3></div>

<p>The more challenging problems are those with inequality constraints. A common way to solve them is to reduce them to unconstrained problems by adding a <a href="Barrier_function" title="Barrier function">barrier function</a>, enforcing the inequality constraints, to the objective function. Such methods are called <a href="Interior_point_methods" class="mw-redirect" title="Interior point methods">interior point methods</a>.<sup id="cite_ref-:2_7-8" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.11">: chpt.11 </span></sup>They have to be initialized by finding a feasible interior point using by so-called <i>phase I</i> methods, which either find a feasible point or show that none exist. Phase I methods generally consist of reducing the search in question to a simpler convex optimization problem.<sup id="cite_ref-:2_7-9" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: chpt.11">: chpt.11 </span></sup>

</p><p>Convex optimization problems can also be solved by the following contemporary methods:<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Subgradient_method#Subgradient-projection_&_bundle_methods" title="Subgradient method">Bundle methods</a> (Wolfe, Lemaréchal, Kiwiel), and</li>

<li><a href="Subgradient_method#Subgradient-projection_&_bundle_methods" title="Subgradient method">Subgradient projection</a> methods (Polyak),</li>

<li><a href="Interior-point_methods" class="mw-redirect" title="Interior-point methods">Interior-point methods</a>,<sup id="cite_ref-Nesterov_1994_1-1" class="reference"><a href="#cite_note-Nesterov_1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> which make use of <a href="Self-concordant_function" title="Self-concordant function">self-concordant</a> barrier functions <sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> and self-regular barrier functions.<sup id="cite_ref-PengRoos2002_14-0" class="reference"><a href="#cite_note-PengRoos2002-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Cutting-plane_methods" class="mw-redirect" title="Cutting-plane methods">Cutting-plane methods</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid method</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li>

<li><a href="Drift_plus_penalty" title="Drift plus penalty">Dual subgradients and the drift-plus-penalty method</a></li></ul>

<p>Subgradient methods can be implemented simply and so are widely used.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> Dual subgradient methods are subgradient methods applied to a <a href="Duality_(optimization)" title="Duality (optimization)">dual problem</a>. The <a href="Drift_plus_penalty" title="Drift plus penalty">drift-plus-penalty</a> method is similar to the dual subgradient method, but takes a time average of the primal variables.

</p>

<div class="mw-heading mw-heading2"><h2 id="Lagrange_multipliers">Lagrange multipliers</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Lagrange_multiplier" title="Lagrange multiplier">Lagrange multiplier</a></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>Consider a convex minimization problem given in standard form by a cost function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math></span><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"></span> and inequality constraints <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x)\leq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x)\leq 0}</annotation>

</semantics>

</math></span><img src="./727fa540a39fcd8b885865e6ea70311b00f82529.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.309ex; height:2.843ex;" alt="{\displaystyle g_{i}(x)\leq 0}" loading="lazy"></span> for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m}</annotation>

</semantics>

</math></span><img src="./be7492673ec3919cb5774b3ba4bb81a7c2365c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq m}" loading="lazy"></span>. Then the domain <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {X}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}}</annotation>

</semantics>

</math></span><img src="./8c7e5461c5286852df4ef652fca7e4b0b63030e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.875ex; height:2.176ex;" alt="{\displaystyle {\mathcal {X}}}" loading="lazy"></span> is:

</p>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.}</annotation>

</semantics>

</math></span><img src="./69b666ea6ee1bd3990a436f521427b58841ee7fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.794ex; height:2.843ex;" alt="{\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.}" loading="lazy"></span></dd></dl>

<p>The Lagrangian function for the problem is<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup>

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).}</annotation>

</semantics>

</math></span><img src="./ccdbbe038598cd0d5519efa636433fc1c0a981e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:58.299ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).}" loading="lazy"></span></dd></dl>

<p>For each point <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> that minimizes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>, there exist real numbers <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}</annotation>

</semantics>

</math></span><img src="./202e557ccd7be929102c908f004a074a71554794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.708ex; height:2.509ex;" alt="{\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}" loading="lazy"></span> called <a href="Lagrange_multipliers" class="mw-redirect" title="Lagrange multipliers">Lagrange multipliers</a>, that satisfy these conditions simultaneously:

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> minimizes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}</annotation>

</semantics>

</math></span><img src="./43bc6ef94c9d00f3b42ee588ce222e3a12020a4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.643ex; height:2.843ex;" alt="{\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}" loading="lazy"></span> over all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in X,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in X,}</annotation>

</semantics>

</math></span><img src="./d6ff919e05d1a505d6efe3da028d2a15b0540783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.623ex; height:2.509ex;" alt="{\displaystyle y\in X,}" loading="lazy"></span></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}</annotation>

</semantics>

</math></span><img src="./28add131d5f3342ba66b38a0e3d1203d68258cb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.969ex; height:2.509ex;" alt="{\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}" loading="lazy"></span> with at least one <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{k}>0,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{k}>0,}</annotation>

</semantics>

</math></span><img src="./5d2415e1d4e77a55ce34d475258fa89acde11f03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.352ex; height:2.509ex;" alt="{\displaystyle \lambda _{k}>0,}" loading="lazy"></span></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}</annotation>

</semantics>

</math></span><img src="./a3dc52b4545e3683de11b80cff4f3f839fb81eb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.846ex; height:2.843ex;" alt="{\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}" loading="lazy"></span> (complementary slackness).</li></ol>

<p>If there exists a "strictly feasible point", that is, a point <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math></span><img src="./bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"></span> satisfying

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}</annotation>

</semantics>

</math></span><img src="./f6b38c752f4463dafc0e1033ea910b62a74145ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.828ex; height:2.843ex;" alt="{\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}" loading="lazy"></span></dd></dl>

<p>then the statement above can be strengthened to require that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{0}=1}</annotation>

</semantics>

</math></span><img src="./fa16d153a3c3adfe6fcd7fea6759705b090d21e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.67ex; height:2.509ex;" alt="{\displaystyle \lambda _{0}=1}" loading="lazy"></span>.

</p><p>Conversely, if some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> satisfies (1)–(3) for <a href="Scalar_(mathematics)" title="Scalar (mathematics)">scalars</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0},\ldots ,\lambda _{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{0},\ldots ,\lambda _{m}}</annotation>

</semantics>

</math></span><img src="./9f890d3da8a9a2d1b37b2387ef0df347f60f3d1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.618ex; height:2.509ex;" alt="{\displaystyle \lambda _{0},\ldots ,\lambda _{m}}" loading="lazy"></span> with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{0}=1}</annotation>

</semantics>

</math></span><img src="./fa16d153a3c3adfe6fcd7fea6759705b090d21e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.67ex; height:2.509ex;" alt="{\displaystyle \lambda _{0}=1}" loading="lazy"></span> then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> is certain to minimize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Software">Software</h2></div>

<p>There is a large software ecosystem for convex optimization. This ecosystem has two main categories: <i>solvers</i> on the one hand and <i>modeling tools</i> (or <i>interfaces</i>) on the other hand.

</p><p>Solvers implement the algorithms themselves and are usually written in C. They require users to specify optimization problems in very specific formats which may not be natural from a modeling perspective. Modeling tools are separate pieces of software that let the user specify an optimization in higher-level syntax. They manage all transformations to and from the user's high-level model and the solver's input/output format.

</p><p>Below are two tables. The first shows shows modelling tools (such as CVXPY and JuMP.jl) and the second solvers (such as SCS and MOSEK). They are by no means exhaustive.

</p>

</caption>

<th>Program

</th>

<th>Language

</th>

<th>Description

</th>

<th><a href="Free_and_open-source_software" title="Free and open-source software">FOSS</a>?

</th>

<th>Ref

</th></tr>

<tr>

<td>CVX

</td>

<td><a href="MATLAB" title="MATLAB">MATLAB</a>

</td>

<td>Interfaces with SeDuMi and SDPT3 solvers; designed to only express convex optimization problems.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>CVXPY

</td>

<td>Python

</td>

<td>

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>Convex.jl

</td>

<td><a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a>

</td>

<td>Disciplined convex programming, supports many solvers.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>CVXR

</td>

</td>

<td>

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>GAMS

</td>

<td>

</td>

<td>Modeling system for linear, nonlinear, mixed integer linear/nonlinear, and second-order cone programming problems.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>GloptiPoly

</td>

<td>MATLAB,

<p>Octave

</p>

</td>

<td>Modeling system for polynomial optimization.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>JuMP.jl

</td>

<td><a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a>

</td>

<td>Supports many solvers. Also supports integer and nonlinear optimization, and some nonconvex optimization.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>ROME

</td>

<td>

</td>

<td>Modeling system for robust optimization. Supports distributionally robust optimization and uncertainty sets.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>SOSTOOLS

</td>

<td>

</td>

<td>Modeling system for polynomial optimization. Uses SDPT3 and SeDuMi. Requires Symbolic Computation Toolbox.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>SparsePOP

</td>

<td>

</td>

<td>Modeling system for polynomial optimization. Uses the SDPA or SeDuMi solvers.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>YALMIP

</td>

<td>MATLAB, Octave

</td>

<td>Interfaces with CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON solvers; also supports integer and nonlinear optimization, and some nonconvex optimization. Can perform <a href="Robust_optimization" title="Robust optimization">robust optimization</a> with uncertainty in LP/SOCP/SDP constraints.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr></tbody></table>

</caption>

<th>Program

</th>

<th>Language

</th>

<th>Description

</th>

<th><a href="Free_and_open-source_software" title="Free and open-source software">FOSS</a>?

</th>

<th>Ref

</th></tr>

<tr>

<td>AIMMS

</td>

<td>

</td>

<td>Can do robust optimization on linear programming (with MOSEK to solve second-order cone programming) and <a href="Mixed_integer_linear_programming" class="mw-redirect" title="Mixed integer linear programming">mixed integer linear programming</a>. Modeling package for LP + SDP and robust versions.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>CPLEX

</td>

<td>

</td>

<td>Supports primal-dual methods for LP + SOCP. Can solve LP, QP, SOCP, and mixed integer linear programming problems.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>CSDP

</td>

</td>

<td>Supports primal-dual methods for LP + SDP. Interfaces available for MATLAB, <a href="R_(programming_language)" title="R (programming language)">R</a>, and Python. Parallel version available. SDP solver.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td><a rel="nofollow" class="external text" href="https://cvxopt.org/">CVXOPT</a>

</td>

<td>Python

</td>

<td>Supports primal-dual methods for LP + SOCP + SDP. Uses Nesterov-Todd scaling. Interfaces to MOSEK and DSDP.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>MOSEK

</td>

<td>

</td>

<td>Supports primal-dual methods for LP + SOCP.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>SeDuMi

</td>

<td>MATLAB, Octave, <a href="MEX_file" title="MEX file">MEX</a>

</td>

<td>Solves LP + SOCP + SDP. Supports primal-dual methods for LP + SOCP + SDP.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>SDPA

</td>

</td>

<td>Solves LP + SDP. Supports primal-dual methods for LP + SDP. Parallelized and extended precision versions are available.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>SDPT3

</td>

<td>MATLAB, Octave, MEX

</td>

<td>Solves LP + SOCP + SDP. Supports primal-dual methods for LP + SOCP + SDP.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>ConicBundle

</td>

<td>

</td>

<td>Supports general-purpose codes for LP + SOCP + SDP. Uses a bundle method. Special support for SDP and SOCP constraints.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>DSDP

</td>

<td>

</td>

<td>Supports general-purpose codes for LP + SDP. Uses a dual interior point method.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr>

<tr>

<td>LOQO

</td>

<td>

</td>

<td>Supports general-purpose codes for SOCP, which it treats as a nonlinear programming problem.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>PENNON

</td>

<td>

</td>

<td>Supports general-purpose codes. Uses an augmented Lagrangian method, especially for problems with SDP constraints.

</td>

<th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No

</th>

</td></tr>

<tr>

<td>SDPLR

</td>

<td>

</td>

<td>Supports general-purpose codes. Uses low-rank factorization with an augmented Lagrangian method.

</td>

<th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</th>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Convex optimization can be used to model problems in a wide range of disciplines, such as automatic <a href="Control_systems" class="mw-redirect" title="Control systems">control systems</a>, estimation and <a href="Signal_processing" title="Signal processing">signal processing</a>, communications and networks, electronic <a href="Circuit_design" title="Circuit design">circuit design</a>,<sup id="cite_ref-:2_7-10" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 17">: 17 </span></sup> data analysis and modeling, <a href="Finance" title="Finance">finance</a>, <a href="Statistics" title="Statistics">statistics</a> (<a href="Optimal_design" class="mw-redirect" title="Optimal design">optimal experimental design</a>),<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> and <a href="Structural_optimization" class="mw-redirect" title="Structural optimization">structural optimization</a>, where the approximation concept has proven to be efficient.<sup id="cite_ref-:2_7-11" class="reference"><a href="#cite_note-:2-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> Convex optimization can be used to model problems in the following fields:

</p>

<ul><li><a href="Portfolio_optimization" title="Portfolio optimization">Portfolio optimization</a>.<sup id="cite_ref-:0_24-0" class="reference"><a href="#cite_note-:0-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup></li>

<li>Worst-case risk analysis.<sup id="cite_ref-:0_24-1" class="reference"><a href="#cite_note-:0-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup></li>

<li>Optimal advertising.<sup id="cite_ref-:0_24-2" class="reference"><a href="#cite_note-:0-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup></li>

<li>Variations of <a href="Regression_analysis" title="Regression analysis">statistical regression</a> (including <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a> and <a href="Quantile_regression" title="Quantile regression">quantile regression</a>).<sup id="cite_ref-:0_24-3" class="reference"><a href="#cite_note-:0-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup></li>

<li>Model fitting<sup id="cite_ref-:0_24-4" class="reference"><a href="#cite_note-:0-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> (particularly <a href="Multiclass_classification" title="Multiclass classification">multiclass classification</a><sup id="cite_ref-:1_25-0" class="reference"><a href="#cite_note-:1-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup>).</li>

<li><a href="Electricity_generation" title="Electricity generation">Electricity generation</a> optimization.<sup id="cite_ref-:1_25-1" class="reference"><a href="#cite_note-:1-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial optimization</a>.<sup id="cite_ref-:1_25-2" class="reference"><a href="#cite_note-:1-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup></li>

<li>Non-probabilistic modelling of <a href="Uncertainty" title="Uncertainty">uncertainty</a>.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup></li>

<li>Localization using wireless signals <sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

<p>Extensions of convex optimization include the optimization of <a href="Biconvex_optimization" title="Biconvex optimization">biconvex</a>, <a href="Pseudo-convex_function" class="mw-redirect" title="Pseudo-convex function">pseudo-convex</a>, and <a href="Quasiconvex" class="mw-redirect" title="Quasiconvex">quasiconvex</a> functions. Extensions of the theory of <a href="Convex_analysis" title="Convex analysis">convex analysis</a> and iterative methods for approximately solving non-convex minimization problems occur in the field of <a href="Convexity_(mathematics)" class="mw-redirect" title="Convexity (mathematics)">generalized convexity</a>, also known as abstract convex analysis.

</p>

<ul><li><a href="Duality_(optimization)" title="Duality (optimization)">Duality</a></li>

<li><a href="Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions" title="Karush–Kuhn–Tucker conditions">Karush–Kuhn–Tucker conditions</a></li>

<li><a href="Optimization_problem" title="Optimization problem">Optimization problem</a></li>

<li><a href="Proximal_gradient_method" title="Proximal gradient method">Proximal gradient method</a></li>

<li><a href="Algorithmic_problems_on_convex_sets" title="Algorithmic problems on convex sets">Algorithmic problems on convex sets</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

<li id="cite_note-Nesterov_1994-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Nesterov_1994_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Nesterov_1994_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFNesterovNemirovskii1994">Nesterov & Nemirovskii 1994</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMurtyKabadi1987" class="citation journal cs1">Murty, Katta; Kabadi, Santosh (1987). "Some NP-complete problems in quadratic and nonlinear programming". <i>Mathematical Programming</i>. <b>39</b> (2): <span class="nowrap">117–</span>129. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02592948">10.1007/BF02592948</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/2027.42%2F6740">2027.42/6740</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:30500771">30500771</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFPardalosVavasis1991" class="citation journal cs1">Pardalos, Panos M.; Vavasis, Stephen A. (1991). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://link.springer.com/article/10.1007/BF00120662">"Quadratic programming with one negative eigenvalue is NP-hard"</a></span>. <i>Journal of Global Optimization</i>. <b>1</b>: <span class="nowrap">15–</span>22. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00120662">10.1007/BF00120662</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFHiriart-UrrutyLemaréchal1996" class="citation book cs1">Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Gdl4Jc3RVjcC&q=lemarechal+convex+analysis+and+minimization"><i>Convex analysis and minimization algorithms: Fundamentals</i></a>. Springer. p. 291. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540568506</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBen-TalNemirovskiĭ2001" class="citation book cs1">Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=M3MqpEJ3jzQC&q=Lectures+on+Modern+Convex+Optimization:+Analysis,+Algorithms,"><i>Lectures on modern convex optimization: analysis, algorithms, and engineering applications</i></a>. pp. <span class="nowrap">335–</span>336. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780898714913</bdi>.</cite></span>

</li>

<li id="cite_note-:2-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-:2_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:2_7-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:2_7-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:2_7-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-:2_7-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-:2_7-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-:2_7-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-:2_7-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-:2_7-8"><sup><i><b>i</b></i></sup></a> <a href="#cite_ref-:2_7-9"><sup><i><b>j</b></i></sup></a> <a href="#cite_ref-:2_7-10"><sup><i><b>k</b></i></sup></a> <a href="#cite_ref-:2_7-11"><sup><i><b>l</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFBoydVandenberghe2004" class="citation book cs1">Boyd, Stephen; Vandenberghe, Lieven (2004). <a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf"><i>Convex Optimization</i></a> <span class="cs1-format">(PDF)</span>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-83378-3</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">12 Apr</span> 2021</span>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.solver.com/convex-optimization">"Optimization Problem Types - Convex Optimization"</a>. 9 January 2011.</cite></span>

</li>

<li id="cite_note-:02-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-:02_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:02_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFArkadi_Nemirovsky2004" class="citation book cs1">Arkadi Nemirovsky (2004). <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=8c3cb6395a35cb504019f87f447d65cb6cf1cdf0"><i>Interior point polynomial-time methods in convex programming</i></a>.</cite></span>

</li>

<cite id="CITEREFAgrawalVerschuerenDiamondBoyd2018" class="citation journal cs1">Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen (2018). <a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/papers/pdf/cvxpy_rewriting.pdf">"A rewriting system for convex optimization problems"</a> <span class="cs1-format">(PDF)</span>. <i>Control and Decision</i>. <b>5</b> (1): <span class="nowrap">42–</span>60. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1709.04494">1709.04494</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F23307706.2017.1397554">10.1080/23307706.2017.1397554</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:67856259">67856259</a>.</cite></span>

</li>

<li id="cite_note-rockafellar93-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-rockafellar93_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFRockafellar,_R._Tyrrell1993" class="citation journal cs1">Rockafellar, R. Tyrrell (1993). <a rel="nofollow" class="external text" href="http://web.williams.edu/Mathematics/sjmiller/public_html/105Sp10/handouts/Rockafellar_LagrangeMultAndOptimality.pdf">"Lagrange multipliers and optimality"</a> <span class="cs1-format">(PDF)</span>. <i>SIAM Review</i>. <b>35</b> (2): <span class="nowrap">183–</span>238. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.7209">10.1.1.161.7209</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1035044">10.1137/1035044</a>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by <a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński</a>, <a href="Dimitri_Bertsekas" title="Dimitri Bertsekas">Bertsekas</a>, and

Boyd and Vandenberghe (interior point).</span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite id="CITEREFNesterovArkadii1995" class="citation book cs1">Nesterov, Yurii; Arkadii, Nemirovskii (1995). <i>Interior-Point Polynomial Algorithms in Convex Programming</i>. Society for Industrial and Applied Mathematics. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0898715156</bdi>.</cite></span>

</li>

<li id="cite_note-PengRoos2002-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-PengRoos2002_14-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFPengRoosTerlaky2002" class="citation journal cs1">Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). "Self-regular functions and new search directions for linear and semidefinite optimization". <i>Mathematical Programming</i>. <b>93</b> (1): <span class="nowrap">129–</span>171. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs101070200296">10.1007/s101070200296</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5610">0025-5610</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:28882966">28882966</a>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite class="citation journal cs1"><span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://link.springer.com/book/10.1007/978-0-387-40065-5">"Numerical Optimization"</a></span>. <i>Springer Series in Operations Research and Financial Engineering</i>. 2006. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-40065-5">10.1007/978-0-387-40065-5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-30303-1</bdi>.</cite></span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><cite id="CITEREFBeavisDobbs1990" class="citation book cs1">Beavis, Brian; Dobbs, Ian M. (1990). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=L7HMACFgnXMC&pg=PA40">"Static Optimization"</a>. <i>Optimization and Stability Theory for Economic Analysis</i>. New York: Cambridge University Press. p. 40. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-33605-8</bdi>.</cite></span>

</li>

<li id="cite_note-:3-17"><span class="mw-cite-backlink">^ <a href="#cite_ref-:3_17-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:3_17-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:3_17-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:3_17-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-:3_17-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-:3_17-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-:3_17-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-:3_17-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-:3_17-8"><sup><i><b>i</b></i></sup></a> <a href="#cite_ref-:3_17-9"><sup><i><b>j</b></i></sup></a> <a href="#cite_ref-:3_17-10"><sup><i><b>k</b></i></sup></a> <a href="#cite_ref-:3_17-11"><sup><i><b>l</b></i></sup></a> <a href="#cite_ref-:3_17-12"><sup><i><b>m</b></i></sup></a> <a href="#cite_ref-:3_17-13"><sup><i><b>n</b></i></sup></a> <a href="#cite_ref-:3_17-14"><sup><i><b>o</b></i></sup></a> <a href="#cite_ref-:3_17-15"><sup><i><b>p</b></i></sup></a> <a href="#cite_ref-:3_17-16"><sup><i><b>q</b></i></sup></a> <a href="#cite_ref-:3_17-17"><sup><i><b>r</b></i></sup></a> <a href="#cite_ref-:3_17-18"><sup><i><b>s</b></i></sup></a> <a href="#cite_ref-:3_17-19"><sup><i><b>t</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFBorchers" class="citation web cs1">Borchers, Brian. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170918180026/http://infohost.nmt.edu/~borchers/presentation.pdf">"An Overview Of Software For Convex Optimization"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://infohost.nmt.edu/~borchers/presentation.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2017-09-18<span class="reference-accessdate">. Retrieved <span class="nowrap">12 Apr</span> 2021</span>.</cite></span>

</li>

<li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.cvxpy.org/">"Welcome to CVXPY 1.1 — CVXPY 1.1.11 documentation"</a>. <i>www.cvxpy.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-04-12</span></span>.</cite></span>

</li>

<li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><cite id="CITEREFUdellMohanZengHong2014" class="citation arxiv cs1">Udell, Madeleine; Mohan, Karanveer; Zeng, David; Hong, Jenny; Diamond, Steven; Boyd, Stephen (2014-10-17). "Convex Optimization in Julia". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1410.4821">1410.4821</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.OC">math.OC</a>].</cite></span>

</li>

<li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.cvxgrp.org/CVXR/">"Disciplined Convex Optimiation - CVXR"</a>. <i>www.cvxgrp.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-06-17</span></span>.</cite></span>

</li>

<li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><cite id="CITEREFLubinDowsonDias_GarciaHuchette2023" class="citation journal cs1">Lubin, Miles; Dowson, Oscar; Dias Garcia, Joaquim; Huchette, Joey; Legat, Benoît; Vielma, Juan Pablo (2023). "JuMP 1.0: Recent improvements to a modeling language for mathematical optimization". <i>Mathematical Programming Computation</i>. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2206.03866">2206.03866</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs12532-023-00239-3">10.1007/s12532-023-00239-3</a>.</cite></span>

</li>

<li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text">Christensen/Klarbring, chpt. 4.</span>

</li>

<li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text">Schmit, L.A.; Fleury, C. 1980: <i>Structural synthesis by combining approximation concepts and dual methods</i>. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260</span>

</li>

<li id="cite_note-:0-24"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_24-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_24-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_24-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:0_24-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-:0_24-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFBoydDiamondZhangAgrawal" class="citation web cs1">Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. <a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf">"Convex Optimization Applications"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151001185038/http://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2015-10-01<span class="reference-accessdate">. Retrieved <span class="nowrap">12 Apr</span> 2021</span>.</cite></span>

</li>

<li id="cite_note-:1-25"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_25-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_25-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:1_25-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFMalick2011" class="citation web cs1">Malick, Jérôme (2011-09-28). <a rel="nofollow" class="external text" href="https://www-ljk.imag.fr//membres/Jerome.Malick/Talks/11-INRIA.pdf">"Convex optimization: applications, formulations, relaxations"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210412044738/https://www-ljk.imag.fr//membres/Jerome.Malick/Talks/11-INRIA.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2021-04-12<span class="reference-accessdate">. Retrieved <span class="nowrap">12 Apr</span> 2021</span>.</cite></span>

</li>

<li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text">Ben Haim Y. and Elishakoff I., Convex Models of Uncertainty in Applied Mechanics, Elsevier Science Publishers, Amsterdam, 1990</span>

</li>

<li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><a href="Ahmad_Bazzi" title="Ahmad Bazzi">Ahmad Bazzi</a>, Dirk TM Slock, and Lisa Meilhac. "Online angle of arrival estimation in the presence of mutual coupling." 2016 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2016.</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBertsekasNedicOzdaglar2003" class="citation book cs1">Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). <i>Convex Analysis and Optimization</i>. Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-45-8</bdi>.</cite></li>

<li><cite id="CITEREFBertsekas2009" class="citation book cs1"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas, Dimitri P.</a> (2009). <i>Convex Optimization Theory</i>. Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-31-1</bdi>.</cite></li>

<li><cite id="CITEREFBertsekas2015" class="citation book cs1"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas, Dimitri P.</a> (2015). <i>Convex Optimization Algorithms</i>. Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-28-1</bdi>.</cite></li>

<li><cite id="CITEREFBorweinLewis2000" class="citation book cs1">Borwein, Jonathan; Lewis, Adrian (2000). <a rel="nofollow" class="external text" href="https://carma.newcastle.edu.au/resources/jon/Preprints/Books/CaNo2/cano2f.pdf"><i>Convex Analysis and Nonlinear Optimization: Theory and Examples, Second Edition</i></a> <span class="cs1-format">(PDF)</span>. Springer<span class="reference-accessdate">. Retrieved <span class="nowrap">12 Apr</span> 2021</span>.</cite></li>

<li><cite id="CITEREFChristensen,_Peter_W.Anders_Klarbring2008" class="citation book cs1">Christensen, Peter W.; Anders Klarbring (2008). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=80IeN__MYI8C"><i>An introduction to structural optimization</i></a>. Vol. 153. Springer Science & Business Media. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781402086663</bdi>.</cite></li></ul>

<ul><li>Hiriart-Urruty, Jean-Baptiste, and <a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a>. (2004). <i>Fundamentals of Convex analysis</i>. Berlin: Springer.</li>

<li><cite id="CITEREFHiriart-UrrutyLemaréchal1993" class="citation book cs1">Hiriart-Urruty, Jean-Baptiste; <a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a> (1993). <i>Convex analysis and minimization algorithms, Volume I: Fundamentals</i>. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 305. Berlin: Springer-Verlag. pp. xviii+417. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-56850-6</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1261420">1261420</a>.</cite></li>

<li><cite id="CITEREFHiriart-UrrutyLemaréchal1993" class="citation book cs1">Hiriart-Urruty, Jean-Baptiste; <a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a> (1993). <i>Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods</i>. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 306. Berlin: Springer-Verlag. pp. xviii+346. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-56852-0</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1295240">1295240</a>.</cite></li>

<li><cite id="CITEREFKiwiel1985" class="citation book cs1">Kiwiel, Krzysztof C. (1985). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/methodsofdescent0000kiwi"><i>Methods of Descent for Nondifferentiable Optimization</i></a></span>. Lecture Notes in Mathematics. New York: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-15642-0</bdi>.</cite></li>

<li><cite id="CITEREFLemaréchal2001" class="citation book cs1"><a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a> (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). <i>Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000</i>. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. <span class="nowrap">112–</span>156. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45586-8_4">10.1007/3-540-45586-8_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-42877-0</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1900016">1900016</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9048698">9048698</a>.</cite></li>

<li><cite id="CITEREFNesterovNemirovskii1994" class="citation book cs1">Nesterov, Yurii; Nemirovskii, Arkadii (1994). <i>Interior Point Polynomial Methods in Convex Programming</i>. SIAM.</cite></li>

<li>Nesterov, Yurii. (2004). <i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=2-ElBQAAQBAJ&dq=%22Introductory+Lectures+on+Convex+Optimization%22&pg=PA1">Introductory Lectures on Convex Optimization</a></i>, Kluwer Academic Publishers</li>

<li><cite id="CITEREFRockafellar1970" class="citation book cs1"><a href="R._Tyrrell_Rockafellar" title="R. Tyrrell Rockafellar">Rockafellar, R. T.</a> (1970). <i>Convex analysis</i>. Princeton: Princeton University Press.</cite></li></ul>

<ul><li><cite id="CITEREFRuszczyński2006" class="citation book cs1"><a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński, Andrzej</a> (2006). <i>Nonlinear Optimization</i>. Princeton University Press.</cite></li>

<li>Schmit, L.A.; Fleury, C. 1980: <i>Structural synthesis by combining approximation concepts and dual methods</i>. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Convex_optimization" class="extiw external" title="commons:Category:Convex optimization">Convex optimization</a></span>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee364a/">EE364a: Convex Optimization I</a> and <a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee364b/">EE364b: Convex Optimization II</a>, Stanford course homepages</li>

<li><a rel="nofollow" class="external text" href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-253-convex-analysis-and-optimization-spring-2012/lecture-notes/">6.253: Convex Analysis and Optimization</a>, an MIT OCW course homepage</li>

<li>Brian Borchers, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170918180026/http://infohost.nmt.edu/~borchers/presentation.pdf">An overview of software for convex optimization</a></li>

<li><a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf">Convex Optimization Book by Lieven Vandenberghe and Stephen P. Boyd</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Convex_analysis_and_variational_analysis174" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_analysis_and_variational_analysis174" style="font-size:114%;margin:0 4em"><a href="Convex_analysis" title="Convex analysis">Convex analysis</a> and <a href="Variational_analysis" title="Variational analysis">variational analysis</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_combination" title="Convex combination">Convex combination</a></li>

<li><a href="Convex_function" title="Convex function">Convex function</a></li>

<li><a href="Convex_set" title="Convex set">Convex set</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="List_of_convexity_topics" title="List of convexity topics">Topics (list)</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Choquet_theory" title="Choquet theory">Choquet theory</a></li>

<li><a href="Convex_geometry" title="Convex geometry">Convex geometry</a></li>

<li><a href="Convex_metric_space" title="Convex metric space">Convex metric space</a></li>

<li><a href="Duality_(optimization)" title="Duality (optimization)">Duality</a></li>

<li><a href="Lagrange_multiplier" title="Lagrange multiplier">Lagrange multiplier</a></li>

<li><a href="Legendre_transformation" title="Legendre transformation">Legendre transformation</a></li>

<li><a href="Locally_convex_topological_vector_space" title="Locally convex topological vector space">Locally convex topological vector space</a></li>

<li><a href="Simplex" title="Simplex">Simplex</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Maps</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_conjugate" title="Convex conjugate">Convex conjugate</a></li>

<li><a href="Concave_function" title="Concave function">Concave</a></li>

<li>(<a href="Closed_convex_function" title="Closed convex function">Closed</a></li>

<li><a href="Logarithmically_convex_function" title="Logarithmically convex function">Logarithmically</a></li>

<li><a href="Proper_convex_function" title="Proper convex function">Proper</a></li>

<li><a href="Pseudoconvex_function" title="Pseudoconvex function">Pseudo-</a></li>

<li><a href="Quasiconvex_function" title="Quasiconvex function">Quasi-</a>) <a href="Convex_function" title="Convex function">Convex function</a></li>

<li><a href="Invex_function" title="Invex function">Invex function</a></li>

<li><a href="Legendre_transformation" title="Legendre transformation">Legendre transformation</a></li>

<li><a href="Semi-continuity" title="Semi-continuity">Semi-continuity</a></li>

<li><a href="Subderivative" title="Subderivative">Subderivative</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Main results (list)</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Carath%C3%A9odory's_theorem_(convex_hull)" title="Carathéodory's theorem (convex hull)">Carathéodory's theorem</a></li>

<li><a href="Ekeland's_variational_principle" title="Ekeland's variational principle">Ekeland's variational principle</a></li>

<li><a href="Fenchel%E2%80%93Moreau_theorem" title="Fenchel–Moreau theorem">Fenchel–Moreau theorem</a></li>

<li><a href="Fenchel-Young_inequality" class="mw-redirect" title="Fenchel-Young inequality">Fenchel-Young inequality</a></li>

<li><a href="Jensen's_inequality" title="Jensen's inequality">Jensen's inequality</a></li>

<li><a href="Hermite%E2%80%93Hadamard_inequality" title="Hermite–Hadamard inequality">Hermite–Hadamard inequality</a></li>

<li><a href="Krein%E2%80%93Milman_theorem" title="Krein–Milman theorem">Krein–Milman theorem</a></li>

<li><a href="Mazur's_lemma" title="Mazur's lemma">Mazur's lemma</a></li>

<li><a href="Shapley%E2%80%93Folkman_lemma" title="Shapley–Folkman lemma">Shapley–Folkman lemma</a></li>

<li><a href="Ursescu_theorem#Robinson–Ursescu_theorem" title="Ursescu theorem">Robinson–Ursescu</a></li>

<li><a href="Ursescu_theorem#Simons'_theorem" title="Ursescu theorem">Simons</a></li>

<li><a href="Ursescu_theorem" title="Ursescu theorem">Ursescu</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Sets</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_hull" title="Convex hull">Convex hull</a></li>

<li>(<a href="Orthogonally_convex_set" class="mw-redirect" title="Orthogonally convex set">Orthogonally</a>, <a href="Pseudoconvexity" title="Pseudoconvexity">Pseudo-</a>) <a href="Convex_set" title="Convex set">Convex set</a></li>

<li><a href="Effective_domain" title="Effective domain">Effective domain</a></li>

<li><a href="Epigraph_(mathematics)" title="Epigraph (mathematics)">Epigraph</a></li>

<li><a href="Hypograph_(mathematics)" title="Hypograph (mathematics)">Hypograph</a></li>

<li><a href="John_ellipsoid" title="John ellipsoid">John ellipsoid</a></li>

<li><a href="Radial_set" title="Radial set">Radial set</a>/<a href="Algebraic_interior" title="Algebraic interior">Algebraic interior</a></li>

<li><a href="Zonotope" class="mw-redirect" title="Zonotope">Zonotope</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Series</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_series#Types_of_subsets" title="Convex series">Convex series related</a> (<a href="Convex_series#Types_of_subsets" title="Convex series">(cs, lcs)-closed</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(cs, bcs)-complete</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(lower) ideally convex</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(H<i>x</i>)</a>, and <a href="Convex_series#Types_of_subsets" title="Convex series">(Hw<i>x</i>)</a>)</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Duality_(optimization)" title="Duality (optimization)">Duality</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dual_system" title="Dual system">Dual system</a></li>

<li><a href="Duality_gap" title="Duality gap">Duality gap</a></li>

<li><a href="Strong_duality" title="Strong duality">Strong duality</a></li>

<li><a href="Weak_duality" title="Weak duality">Weak duality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Applications and related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convexity_in_economics" title="Convexity in economics">Convexity in economics</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-22" href="https://en.wikipedia.org/wiki/?title=Convex_optimization&oldid=1296803862">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>